#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution
{
public:
    int snakesAndLadders(vector<vector<int>> &board)
    {
        //(loops,index)
        size_t n = board.size();
        queue<int> nextLoop;
        vector<bool> vis(n * n, false);
        nextLoop.push(0);
        int loop = 1;
        while (!nextLoop.empty())
        {
            int size = nextLoop.size();
            for (int i = 0; i < size; i++)
            {
                int index = nextLoop.front();
                for (int i = index + 1; i <= min<int>(index + 6, n * n - 1); i++)
                {
                    int next = Sample(board, i);
                    next = next == -2 ? i : next;
                    if (next == n * n - 1)
                    {
                        return loop;
                    }
                    if (!vis[next])
                    {
                        nextLoop.push(next);
                        vis[next] = true;
                    }
                }
                nextLoop.pop();
            }
            loop += 1;
        }
        return -1;
    }

    int Sample(vector<vector<int>> &board, int index)
    {
        // index[0-n^2-1]
        // 0->(n-1,0)
        int n = board.size();
        int y = n - 1 - index / n;
        int x = (index / n) % 2 == 0 ? index % n : n - 1 - (index % n);
        return board[y][x] - 1;
    }
};
int main()
{
    cout << "Code909" << endl;
    Solution s;
    // vector<vector<int>> board = {
    //     {-1, -1, -1, -1, -1, -1},
    //     {-1, -1, -1, -1, -1, -1},
    //     {-1, -1, -1, -1, -1, -1},
    //     {-1, 35, -1, -1, -1, 13},
    //     {-1, -1, -1, -1, -1, -1},
    //     {-1, 15, -1, -1, -1, -1}};
    vector<vector<int>> board = {
        {1, 1, -1},
        {1, 1, 1},
        {-1, 1, 1}};
    cout << s.snakesAndLadders(board) << endl;
    return 0;
}